package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class InsertSort {

  public static void main(String[] args) {
    // int[] arr = {101, 34, 119, 1, -1, 89};
    // 创建要给80000个的随机的数组
    int[] arr = new int[80000];
    for (int i = 0; i < 80000; i++) {
      arr[i] = (int) (Math.random() * 80000); // 生成一个[0, 8000000) 数
    }

    System.out.println("插入排序前");
    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);

    insertSort(arr); // 调用插入排序算法

    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序前的时间是=" + date2Str);

    // System.out.println(Arrays.toString(arr));
  }

  // 插入排序，依次将每个元素，“向前"挪到正确的位置上, 从小到大排序！
  // 例如
  public static void insertSort(int[] arr) {
    int insertVal = 0; // 当前需要为其找位置的元素值
    int insertIndex = 0; // insertIndex下标上的元素 <  insertVal
    // 遍历每个元素
    for (int i = 1; i < arr.length; i++) {
      // 定义待插入的数
      insertVal = arr[i];
      insertIndex = i - 1; // 即arr[1]的前面这个数的下标

      // 给insertVal 找到插入的位置
      // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
      // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
      // 3. 就需要将 arr[insertIndex] 后移
      while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
        arr[insertIndex + 1] = arr[insertIndex]; // 前面的元素向后挪，不需要像冒泡那样互换元素
        insertIndex--;
      }
      // 当退出while循环时，说明插入的位置找到, 即 insertIndex + 1
      arr[insertIndex + 1] = insertVal;
    }
  }
}
